The present disclosure presents advancement in the state of the art for scheduled systems, modeled as sets of tasks and resources, in which the tasks are periodic, i.e., a resource must dedicate some required amount of service at some required frequency to the tasks during each resource schedule period. Such systems generally include (1) sets of tasks; (2) sets of resources that service the tasks; and (3) schedulers for assigning resources to tasks, with the attribute that some of tasks need to be serviced periodically. Such systems are embodied in many physical forms, but of immediate relevance to this invention are computer software and hardware systems. The resources may have different service rates/capacities and the tasks may have different frequencies, or equivalently, different periods.
A scheduler or schedulers are responsible for assigning resources to tasks in such a way as to meet some set of system objectives. Such systems span a very broad range of applications, including but not limited to computer operating systems, transportation networks, manufacturing and industrial processes, analog, digital, and optical communication systems, wireless communication systems, packet switched communications networks (e.g., IP networks), cell switched communications networks (e.g., ATM networks), precision counting, sampling, and measuring devices, cryptographic systems, and electromagnetic signaling devices (e.g., magnetic resonance imaging systems). Such systems can be modeled as being composed of periodic tasks, resources, and schedulers.
In such systems, a primary challenge is for the scheduler to find collision-free schedules, i.e., schedules defining which tasks are serviced by which resources at which times such that no more than one task is scheduled for servicing by a resource or set of resources at any time, if such a schedule exists, and such that the resources are highly utilized. An additional challenge is to dynamically add new periodic tasks to the schedule such that the collision-free property of the schedule is maintained. In some environments, e.g., packet switched networks, cell switched networks, and distributed operating systems, an additional complication is the need to coordinate schedules across distributed resources. For example, a packet flow in a packet switched network typically traverses multiple packet switches/routers and interconnecting communication links. The flow needs be scheduled locally at each router, and then the local schedules at each router along the path need to be coordinated in time (scheduled) to provide an end-to-end schedule. Distributed operating systems have a similar challenge in that processes being executed on different hosts need to be globally coordinated in time.
In terms of computational complexity, in general collision-free scheduling problems are NP-hard (intractable) when certain optimality criteria are imposed. The precise definition of an NP-hard scheduling problem is somewhat complex but well understood by those skilled in the art; a practical definition is that an NP-hard scheduling problem is one in which the time needed for an optimal solution method to solve the problem grows exponentially (very) fast with respect to the size of the problem. In practice, optimal solution methods for NP-hard scheduling problems are not used except for when they may be applied to relatively small problems.
As a result, a variety of approximation algorithms for scheduling have been developed to provide near-optimal schedules, and/or certain constraints have been added to the problem to improve the performance of algorithms. See, for example, D. Peng et al. “Assignment and Scheduling Communicating Periodic Tasks in Distributed Real-Time Systems”, IEEE Transactions on Software Engineering, Vol. 23, No. 12, December 1997, and the references therein for a survey of periodic scheduling problems and algorithms for operating systems, the disclosure of which is incorporated herein by reference. In the area of packet-switched networks, H. Zhang, D. Ferrari, “Rate-Controlled Service Disciplines”, Journal of High Speed Networks: Special Issue on Quality of Service, Vol. 3, No. 4, 1994, and the references therein, the disclosure of which is incorporated herein by reference, provide an overview of the state-of-the-art with respect to rate-controlled packet flows, which can be modeled as periodic tasks in packet communication networks. In both the operating systems and packet-switched networks literature, scheduling approximation algorithms that account for and exploit the periodic attribute of the tasks have been described.
Constructing schedules that specify which resources will service which tasks during specific intervals is a difficult problem, whether or not the tasks need periodic servicing. Accordingly, the present invention affords improved computational complexity for computing schedules and affords improved performance of those schedules with respect to resource utilization.